package cn.edu.ncepu;

import java.math.BigInteger;

public class BinaryExponentiation {

    /**
     * 二进制快速幂算法（大数版）
     * @param base 底数（BigInteger类型，支持极大数）
     * @param power 指数（非负整数）
     * @return base^power 的结果
     */
    public static BigInteger binaryExponentiation(BigInteger base, int power) {
        // 处理指数为0的特殊情况：任何数的0次方为1
        if (power == 0) {
            return BigInteger.ONE;
        }
        int power2 = 1; // 对应Python中的power_2，记录当前二进制位权重（2^0, 2^1, 2^2...）
        BigInteger result = BigInteger.ONE; // 结果初始值为1
        BigInteger p = base; // 临时变量，初始为底数，每次循环平方

        while (power2 <= power) {
            // 位运算判断当前位是否为1（等价于power & power2 != 0）
            if ((power2 & power) != 0) {
                result = result.multiply(p); // 结果乘以当前p
            }
            p = p.multiply(p); // p平方
            power2 = power2 << 1; // 左移1位，等价于×2
        }
        return result;
    }

    public static void main(String[] args) {
        // 测试用例1：3^100
        BigInteger base1 = BigInteger.valueOf(3);
        int power1 = 100;
        BigInteger result1 = binaryExponentiation(base1, power1);
        BigInteger expected1 = base1.pow(power1); // Java自带的pow方法作为对照
        System.out.println("3^100 自定义实现：" + result1);
        System.out.println("3^100 Java自带方法：" + expected1);
        System.out.println("是否相等：" + result1.equals(expected1));

        System.out.println("------------------------");

        // 测试用例2：32^15
        BigInteger base2 = BigInteger.valueOf(32);
        int power2 = 15;
        BigInteger result2 = binaryExponentiation(base2, power2);
        BigInteger expected2 = base2.pow(power2);
        System.out.println("32^15 自定义实现：" + result2);
        System.out.println("32^15 Java自带方法：" + expected2);
        System.out.println("是否相等：" + result2.equals(expected2));
    }
}